var intervalSchedule = function (intvs) {
    if (intvs.length === 0) return 0;
    // 按end升序排序
    intvs.sort((a, b) => {
        if (a[1] < b[1])
            return -1;
        else if (a[1] > b[1])
            return 1;
        else return 0;
    })

    // 至少有一个区间不相交
    let count = 1;

    // 排序后，第一个区间就是 x
    let x_end = intvs[0][1];
    for (let interval of intvs) {
        let start = interval[0];
        if (start >= x_end) {
            // 找到下一个选择的区间了
            count++;
            x_end = interval[1];
        }
    }
    return count;
}


let a = [[1, 5], [1, 6], [1, 3], [1, 4], [2, 4], [2, 3], [3, 8], [3, 4], [4, 6]]

let a_sort = a.sort((a, b) => {
    if (a[1] < b[1])
        return -1;
    else if (a[1] > b[1])
        return 1;
    else return 0;
})
console.log(a)
console.log(a_sort)

console.log(intervalSchedule(a))


/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function (intervals) {
    let n = intervals.length;
    // 我们已经会求最多有几个区间不会重叠了，那么剩下的不就是至少需要去除的区间吗？
    return n - intervalSchedule(intervals);
};


var findMinArrowShots = function (intvs) {
    if (intvs.length === 0) return 0;
    // 按end升序排序
    intvs.sort((a, b) => {
        if (a[1] < b[1])
            return -1;
        else if (a[1] > b[1])
            return 1;
        else return 0;
    })

    // 至少有一个区间不相交
    let count = 1;

    // 排序后，第一个区间就是 x
    let x_end = intvs[0][1];
    for (let interval of intvs) {
        let start = interval[0];
        if (start > x_end) {
            // 找到下一个选择的区间了
            count++;
            x_end = interval[1];
        }
    }
    return count;
};